Twierdzenie Tutte’a i twierdzenie Halla

W tym miesiącu w Kąciku Początkującego Olimpijczyka (patrz ostatnia strona Delty) kontynuujemy temat skojarzeń w grafach. Są z nim związane dwa ważne twierdzenia: Tutte’a i Halla. Ich uzasadnienia są bardzo pouczające, a ponieważ nie udałoby mi się ich zmieścić na ostatniej stronie, przedstawiam je w niniejszym artykule, Kącikowi pozostawiając same zadania z rozwiązaniami.

Przed przystąpieniem do lektury zachęcamy Czytelnika do zapoznania się z Kącikiem Początkującego Olimpijczyka nr 68 i 69 w ${\mathrm{\Delta }}_{24}^8$ i ${\mathrm{\Delta }}_{24}^9$. Są tam wszystkie niezbędne definicje.

Zaczniemy od podstawowego narzędzia. Niech $M$ będzie skojarzeniem w grafie $G.$ Ścieżkę nazywamy naprzemienną dla skojarzenia $M,$ jeśli ma krawędzie na zmianę nienależące i należące do $M.$

Lemat o ścieżce naprzemiennej. Jeśli istnieje ścieżka naprzemienna łącząca pewne dwa wierzchołki grafu $G$ nienależące do skojarzenia $M,$ to skojarzenie $M$ nie jest największe.

Dowód: Niech $P$ będzie opisaną w lemacie ścieżką naprzemienną. Ze skojarzenia $M$ usuńmy te krawędzie, które należą do $P$ i zamiast tego dołączmy te krawędzie $P,$ które nie były wcześniej w $M.$ W ten sposób otrzymujemy podgraf $M^{\prime },$ który ma o jedną krawędź więcej niż $M.$

Ten podgraf jest nadal skojarzeniem, gdyż w wyniku przeprowadzonej powyżej operacji stopnie wierzchołków $a$ i $b$ wzrosły z $0$ do $1,$ a pozostałe nie zmieniły się. $◻$

Ścieżka opisana w lemacie nazywana jest często ścieżką powiększającą skojarzenie.

Wprowadźmy teraz definicje potrzebne do sformułowania twierdzenia Tutte’a.

Graf nazywamy spójnym, jeśli każde dwa jego wierzchołki połączone są ścieżką. Każdy maksymalny (w sensie relacji bycia podgrafem) podgraf spójny danego grafu nazywamy jego spójną składową. Spójne składowe o parzystej liczbie wierzchołków będziemy nazywać parzystymi, a o nieparzystej – nieparzystymi. Oznaczmy przez $\mathcal{O}(G)$ liczbę nieparzystych spójnych składowych grafu $G.$

Niech $G=(V,E)$ będzie grafem i niech $S⊊V.$ Przez $G-S$ rozumiemy graf $G$ z usuniętymi wszystkimi wierzchołkami należącymi do $S$ oraz usuniętymi wszystkimi krawędziami, które mają co najmniej jeden koniec w zbiorze $S.$

Twierdzenie Tutte’a. Graf $G=(V,E)$ ma skojarzenie pełne wtedy i tylko wtedy, gdy $$\begin{array}{}\text{(T)}& \underset{S⊊V}{\mathrm{\forall }}\mathcal{O}(G-S)\le |S|.\end{array}$$

Zbiory $S$ spełniające warunek $\mathcal{O}(G-S)\le |S|$ będziemy nazywać dobrymi, a niespełniające go – niedobrymi. Zwróćmy uwagę, że odrzucamy tu $S=V$ (wtedy $G-S$ nie jest grafem, choć nawet jeśli dopuścimy graf pusty, to ma on 0 składowych nieparzystych), ale uwzględniony jest zbiór pusty. Dla $S=\mathrm{\varnothing }$ otrzymujemy w warunku $\text{(T)}$, że $\mathcal{O}(G)=0,$ czyli każda spójna składowa grafu $G$ jest parzysta. Jest to oczywisty warunek konieczny istnienia skojarzenia pełnego.

Dowód ($\Rightarrow$). Zakładamy, że graf $G=(V,E)$ ma skojarzenie pełne. Należy wykazać, że każdy zbiór $S⊊V$ jest dobry. Dla $S=\mathrm{\varnothing }$ już to zrobiliśmy, niech więc $|S|\ge 1.$ Każda nieparzysta spójna składowa grafu $G-S$ ma przynajmniej jeden wierzchołek, który jest skojarzony z wierzchołkiem spoza niej. Nie może on należeć do innej spójnej składowej, więc musi należeć do zbioru $S.$ Każdej spójnej składowej grafu $G-S$ można w ten sposób przypisać pewien wierzchołek ze zbioru $S.$ To przyporządkowanie jest różnowartościowe (bo idzie wzdłuż krawędzi skojarzenia), więc $\mathcal{O}(G-S)\le |S|.$

Dowód ($\Leftarrow$). Teraz zakładamy, że spełniony jest warunek $\text{(T)}$. Dla dowodu nie wprost dodatkowo przypuśćmy, że w grafie $G$ nie ma skojarzenia pełnego. Wówczas graf $G$ ma parzystą liczbę wierzchołków (warunek $\text{(T)}$ dla $S=\mathrm{\varnothing }$) i nie jest grafem pełnym.

Niech $G^{\prime }=G+e$ będzie grafem $G$ z dodaną krawędzią $e.$ Graf $G^{\prime }$ nadal spełnia warunek $\text{(T)}$, ponieważ dla dowolnego $S⊊V$ zachodzi $\mathcal{O}(G^{\prime }-S)\le \mathcal{O}(G-S).$ Istotnie, krawędź $e$ może łączyć wierzchołki:

• z których co najmniej jeden należy do $S$;

• z tej samej spójnej składowej grafu $G-S$;

• z różnych parzystych spójnych składowych grafu $G-S$;

• z parzystej i nieparzystej składowej grafu $G-S$;

• z różnych nieparzystych spójnych składowych grafu $G-S.$

W pierwszych czterech przypadkach mamy $\mathcal{O}(G^{\prime }-S)=\mathcal{O}(G-S),$ a w ostatnim $\mathcal{O}(G^{\prime }-S)=\mathcal{O}(G-S)-2.$ Możemy zatem przyjąć bez utraty ogólności, że dodanie jakiejkolwiek krawędzi spowoduje zaistnienie skojarzenia pełnego.

Niech $U$ będzie zbiorem wszystkich wierzchołków grafu $G$ o stopniu $|V|-1,$ czyli wierzchołków połączonych z każdym innym. Wykażemy, że zbiór $U$ jest niedobry, co będzie poszukiwaną sprzecznością.

Zauważmy najpierw, że nie wszystkie spójne składowe grafu $G-U$ są klikami – inaczej graf $G$ miałby skojarzenie pełne.

W każdej spójnej składowej można by było dowolnie połączyć w pary wszystkie wierzchołki oprócz najwyżej jednego. Niesparowanych wierzchołków w składowych jest dokładnie $\mathcal{O}(G-U),$ więc możemy je połączyć z różnymi wierzchołkami ze zbioru $U.$ Pozostałe wierzchołki ze zbioru $U$ dowolnie łączymy w pary.

Teraz wykażemy, że w grafie $G$ istnieje struktura widoczna na rysunku obok (linia przerywana oznacza tu brak sąsiedztwa). Niech $S_0$ będzie spójną składową grafu $G-U$ niebędącą kliką. Ma ona zatem dwa wierzchołki $x$ i $y,$ które nie są połączone krawędzią. Wierzchołki $a,$ $c,$ $b$ wybieramy jako trzy kolejne na najkrótszej ścieżce łączącej $x$ i $y.$ Ponadto $c\notin U,$ więc istnieje wierzchołek $d\in V,$ z którym $c$ nie jest połączony.

Wobec poczynionych wcześniej założeń, w grafie $G+ab$ znajdziemy pewne skojarzenie pełne $M_1,$ a w grafie $G+cd$ – skojarzenie pełne $M_2.$ Ponieważ w $G$ nie było skojarzenia pełnego, więc krawędź $ab$ należy do skojarzenia $M_1,$ a $cd$ – do $M_2.$ Skojarzenie $M_1-\{a,b\}$ ma o jedną krawędź mniej niż miałoby skojarzenie pełne w grafie $G,$ analogicznie skojarzenie $M_2-\{c,d\}.$ Wystarczy zatem znaleźć ścieżkę powiększającą któreś z tych skojarzeń.

Sumą skojarzeń $M_1$ i $M_2$ jest multigraf $H,$ w którym wszystkie wierzchołki są stopnia $2.$ Taki multigraf jest sumą parami rozłącznych cykli, być może o długości $2.$ W każdym takim cyklu krawędzie z $M_1$ i $M_2$ występują na przemian.

Jeśli krawędzie $ab$ i $cd$ leżą na rozłącznych cyklach, odpowiednio $C_1$ i $C_2,$ to ścieżka $C_1-ab$ powiększa skojarzenie $M_1-\{a,b\}$ w grafie $G.$ Pozostaje przypadek, gdy $ab$ i $cd$ leżą na jednym cyklu. Możemy przyjąć, że wierzchołki $a,$ $b,$ $c,$ $d$ leżą na tym cyklu w tejże kolejności. Wówczas ścieżka od $c$ do $d$ powiększa skojarzenie $M_2-\{c,d\}$ w grafie $G.$ $◻$

Można powiedzieć, że twierdzenie Tutte’a pozwala stwierdzić, czy w danej klasie, w której wiadomo, kto z kim się lubi, możemy usadzić uczniów w ławkach w taki sposób, że każdy siedzi z kimś, kogo lubi. A co, jeśli dodatkowo chcemy, by w każdej ławce siedzieli chłopiec i dziewczynka? Tu wygodnego kryterium dostarcza twierdzenie Halla, które omawiamy poniżej.

Ale najpierw potrzebne definicje. Grafem dwudzielnym o dwupodziale $(A,B)$ nazywamy taki graf, w którym zbiór wierzchołków jest sumą rozłącznych zbiorów $A$ i $B,$ ponadto każda krawędź ma jeden koniec w $A,$ a drugi w $B.$ Mówimy, że skojarzenie $M$ nasyca zbiór $A,$ jeśli każdy wierzchołek ze zbioru $A$ należy do $M.$

Niech $G=(V,E)$ będzie grafem i niech $U\subseteq V.$ Sąsiedztwem zbioru $U$ nazywamy zbiór tych wierzchołków spoza $U,$ które mają co najmniej jednego sąsiada w $U.$ Oznaczamy je przez $N_G(U).$ Jeśli jest oczywiste, o jaki graf chodzi, to można pisać po prostu $N(U).$

Twierdzenie Halla. Graf dwudzielny $G$ o dwupodziale $(A,B)$ ma skojarzenie nasycające zbiór $A$ wtedy i tylko wtedy, gdy $$\begin{array}{}\text{(H)}& \underset{S\subseteq A}{\mathrm{\forall }}|N_G(S)|\ge |S|.\end{array}$$ Dowód ($\Rightarrow$). Załóżmy, że graf ma skojarzenie $M$ nasycające zbiór $A.$ Niech $S=s_1,s_2,\dots ,s_m\subseteq A$ będzie dowolny. Przez $s_i^{\prime }\in B$ oznaczmy unikalnego sąsiada wierzchołka $s_i$ w skojarzeniu $M.$ Wówczas $s_1^{\prime },s_2^{\prime },\dots ,s_m^{\prime }\in N(S)$ są różne, więc $|N(S)|\ge m=|S|.$

Dowód ($\Leftarrow$). Niech $M$ będzie największym skojarzeniem w grafie $G.$ Przypuśćmy, że skojarzenie $M$ nie nasyca zbioru $A.$ Udowodnimy, że warunek $\text{(H)}$ nie jest wtedy spełniony.

Na mocy przypuszczenia nie wprost, pewien wierzchołek $a\in A$ nie należy do skojarzenia $M.$ Rozważmy wszystkie wierzchołki grafu $G$ połączone z wierzchołkiem $a$ za pomocą ścieżek naprzemiennych dla skojarzenia $M.$ Niech $S$ oznacza tę część spośród wspomnianych wierzchołków, która należy do zbioru $A,$ razem z wierzchołkiem $a,$ natomiast $T$ – tę część, która jest w zbiorze $B.$ Każda ścieżka naprzemienna rozpoczęta w wierzchołku $a$ i zakończona w wierzchołku należącym do $T$ może być kontynuowana – w przeciwnym razie otrzymalibyśmy ścieżkę powiększającą skojarzenie $M.$ W takim razie z każdym wierzchołkiem $t\in T$ możemy związać wierzchołek $s\in S,$ który pojawia się bezpośrednio po $t$ na pewnej ścieżce naprzemiennej, startującej z $a.$ Wierzchołek $s$ jest wyznaczony jednoznacznie, gdyż krawędź $ts$ należy do skojarzenia $M$ (a w skojarzeniu nie mogą pojawić się krawędzie $ts$ i $t{s}^{\prime }$ dla $s\ne s^{\prime }$). Dokładnie tak samo uzasadniamy, że różnym wierzchołkom z $T$ odpowiadają różne wierzchołki z $S,$ i że są one różne od $a.$ Dowodzimy w ten sposób, że $|S|>|T|.$

Jest jasne, że $T\subseteq N(S).$ Wykażemy, że zachodzi tu równość. Niech $w\in N(S)$ – wtedy ma on sąsiada $s\in S,$ więc albo $s=a$ (i wtedy $w\in T$), albo istnieje ścieżka naprzemienna $P$ o kolejnych wierzchołkach $a,\dots ,t,s.$ Krawędź $ts$ należy do skojarzenia $M,$ więc krawędź $sw$ nie może do niego należeć. Wobec tego ścieżka o kolejnych wierzchołkach $a,\dots ,t,s,w$ jest naprzemienna i w konsekwencji $w\in T.$

Wobec powyższych rozważań $|S|>|T|=|N(S)|$ i warunek $\text{(H)}$ nie jest spełniony, co kończy dowód. $◻$

Przykłady zastosowań oraz zadania Czytelnik znajdzie na ostatniej stronie niniejszego numeru Delty.